package bfsAndDfs

/*
拓扑排序
*/

// BFS（Kahn算法）
func loudAndRich(richer [][]int, quiet []int) []int {
	var (
		edges = make([][]int, len(quiet))
		// 记录节点的入度
		inDegree = make([]int, len(quiet))
		queue    []int
		// 记录比当前节点富有且安静值最小的节点的索引
		ans = make([]int, len(quiet))
		// 记录比当前富有且安静值最小的节点的安静值
		value = make([]int, len(quiet))
	)
	// 构造邻接表
	for _, info := range richer {
		// 如果x比y富有，则x->y
		edges[info[0]] = append(edges[info[0]], info[1])
		inDegree[info[1]]++
	}

	// 遍历入度列表，将入度为0的节点存入队列
	for i, v := range inDegree {
		if v == 0 {
			// 这里是将节点值压入队列（写快了容易将v压入队列，v总是0，所以会导致结果错误）
			queue = append(queue, i)
		}
		// 初始化时，比自己富有且安静值最小的节点就是自己
		ans[i] = i
		value[i] = quiet[i]
	}

	// BFS(Kahn算法-拓扑排序)
	for len(queue) != 0 {
		e := queue[0]
		queue = queue[1:]
		// 遍历节点e的邻接节点
		for _, v := range edges[e] {
			if value[v] > value[e] {
				// 如果当前节点的父节点（比自己富有）的最小安静值比自己的小，则取父节点的安静值
				value[v] = value[e]
				ans[v] = ans[e]
			}
			// 将邻接节点入度-1，如果遇到入度为0的节点，存入队列
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	return ans
}

// 带缓存的DFS
func loudAndRich1(richer [][]int, quiet []int) []int {
	var (
		edges  = make([][]int, len(quiet))
		answer = make([]int, len(quiet))
		// 该dfs函数返回比node节点更富有的节点中安静值最小的节点
		dfs func(node int) int
	)

	// 构造邻接表，如果A比B富有，则构造B->A(子节点比父节点富有)
	for _, info := range richer {
		edges[info[1]] = append(edges[info[1]], info[0])
	}

	// 将所有answer初始化为-1,相等于设置为未搜索状态
	// 如果answer[i] != -1说明处于搜索中或已搜索完成状态，而题目不存在环（因为不可能存在比自己富有又比自己穷的人）
	// 即在dfs过程中不可能遇到搜索中状态的节点，如果answer[i]！=1说明当前节点已搜索完
	for i := 0; i < len(quiet); i++ {
		answer[i] = -1
	}

	// dfs中，先设置node的状态（也可没有，按需使用）,然后遍历当前节点的所有邻接节点，对邻接节点dfs，然后更新当前节点状态
	dfs = func(node int) int {
		if answer[node] == -1 {
			answer[node] = node
			for _, e := range edges[node] {
				// 获取比邻接节点更富有且最安静的节点
				t := dfs(e)
				// 注意这里用的是quiet[answer[node]]而不是quiet[node]，因为answer[node]存储的是当前找到的比node更富有且最安静的节点
				// 用它去与node的邻接节点的更富有最安静节点比较,取更小的值
				if quiet[answer[node]] > quiet[t] {
					answer[node] = t
				}
			}
		}
		return answer[node]
	}

	// 遍历每个节点，对每个节点都进行一次dfs
	for i := 0; i < len(quiet); i++ {
		dfs(i)
	}
	return answer
}
